package leetcode._05_二叉树;

import org.junit.Test;

import java.util.HashMap;

/**
 * @author pppppp
 * @date 2022/3/31 10:34
 * 给定两个整数数组 preorder 和 inorder ，
 * 其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 * 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * 输出: [3,9,20,null,null,15,7]
 * 示例 2:
 * 输入: preorder = [-1], inorder = [-1]
 * 输出: [-1]
 */
public class _105_从前序与中序遍历序列构造二叉树 {

    @Test
    public void T_0() {
        int[][] inorder = {{9, 3, 15, 20, 7}, {-1}};
        int[][] preorder = {{3, 9, 20, 15, 7}, {-1}};

        // int [] ans = {3,9,20,null,null,15,7};
        for (int i = 0; i < inorder.length; i++) {
            TreeNode node = buildTree_0(preorder[i], inorder[i]);
            System.out.println();
        }
    }

    HashMap<Integer, Integer> map = new HashMap<>();
    Integer rootIndex;
    int[] preorder;
    int[] inorder;

    public TreeNode buildTree_0(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        rootIndex = 0;
        this.preorder = preorder;
        this.inorder = inorder;
        TreeNode treeNode = buildTreeAssit(0, preorder.length - 1);
        return treeNode;
    }

    private TreeNode buildTreeAssit(int leftIndex, int rightIndex) {
        if (leftIndex > rightIndex || rootIndex == preorder.length) {
            return null;
        }
        TreeNode treeNode = new TreeNode(preorder[rootIndex]);
        Integer pos = map.get(preorder[rootIndex]);
        rootIndex++;
        treeNode.left = buildTreeAssit(leftIndex, pos - 1);
        treeNode.right = buildTreeAssit(pos + 1, rightIndex);
        return treeNode;
    }
}
